package 程序员面试金典;

public class 硬币 {

    public int waysToChange(int n) {
        int MOD=1000000007;
        int[] dp = new int[n + 1];
        dp[0]=1;
        int[] coins={1,5,10,25};
        for (int coin : coins) {
            for (int i = coin; i <=n ; i++) {
                dp[i]=(dp[i]+dp[i-coin])%MOD;
            }
        }
        return dp[n];
    }
}
